/**
 * 反转链表
 * 1.定义3个指针, 整体右移,边移动边反转,保证不会断链
 * 2.可以采用头插法思想进行反转
 */
public class suanfa13 {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }

        public ListNode ReverseList1(ListNode head) {
            if (head == null && head.next == null) {
                return head;
            }
            //至少有2个结点
            ListNode left = head;
            ListNode mid = left.next;
            ListNode right = mid.next;//指向第三个结点,有可能为null
            
            while (right != null) {
                mid.next = left;
                left = mid;
                right = right.next;
            }
            mid.next = left;
            head.next = null;//head已经到了链表尾部,将head.next置为空,变为尾节点
            head = mid;//新的头结点为mid
            return head;
        }
        public ListNode ReverseList2(ListNode head) {
            if (head == null ||  head.next == null) {
                return head;
            }
            ListNode newHead = null;
            while (head != null) {
                //把原链表的第一个节点拿下来
                ListNode p = head;
                head = head.next;
                //把节点头插新的链表
                p.next = newHead;
                newHead = p;
            }
            return newHead;
        }

    }
}
